{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #和为 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组和一个整数&nbsp;<code>k</code><strong> ，</strong>请找到该数组中和为&nbsp;<code>k</code><strong>&nbsp;</strong>的连续子数组的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>nums = [1,1,1], k = 2\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 此题 [1,1] 与 [1,1] 为两种不同的情况\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>nums = [1,2,3], k = 3\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li>\n",
    "\t<p><code>-10<sup>7</sup>&nbsp;&lt;= k &lt;= 10<sup>7</sup></code></p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 560&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/subarray-sum-equals-k/\">https://leetcode-cn.com/problems/subarray-sum-equals-k/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [QTMn0o](https://leetcode.cn/problems/QTMn0o/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [QTMn0o](https://leetcode.cn/problems/QTMn0o/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1]\\n2', '[1,2,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     # 暴力解法, 超时\n",
    "#     def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "#         res = 0\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             pre_sum = nums[i]\n",
    "#             if pre_sum == k:\n",
    "#                 res += 1\n",
    "#             for j in range(i + 1, n):\n",
    "#                 pre_sum += nums[j]\n",
    "#                 if pre_sum == k:\n",
    "#                     res += 1\n",
    "#         return res\n",
    "class Solution:\n",
    "    # 使用字典优化, 空间换时间\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = pre_sum = 0\n",
    "        dic = {0 : 1}\n",
    "        for num in nums:\n",
    "            pre_sum += num\n",
    "            res += dic.get(pre_sum - k, 0)\n",
    "            dic[pre_sum] = dic.get(pre_sum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dic={0:1}\n",
    "        sums,res=0,0\n",
    "        for num in nums:\n",
    "            sums+=num\n",
    "            res+=dic.get(sums-k,0)\n",
    "            dic[sums]=dic.get(sums,0)+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # s = 0\n",
    "        # sum_map = {}\n",
    "        # sum_arr = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     s += nums[i]\n",
    "        #     if s not in sum_map:\n",
    "        #         sum_map[s] = []\n",
    "        #     sum_map[s].append(i)\n",
    "        #     sum_arr.append(s)\n",
    "        \n",
    "        # ans = 0\n",
    "        # for i in range(len(nums)):\n",
    "        #     target = sum_arr[i] - k\n",
    "        #     if target in sum_map:\n",
    "        #         values = sum_map[target]\n",
    "        #         ans += len([x for x in values if x < i])\n",
    "        #     if target == 0:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        sum_map = {0: 1}\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            ans += sum_map.get(s - k, 0)\n",
    "            sum_map[s] = sum_map.get(s, 0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     # 暴力解法, 超时\n",
    "#     def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "#         res = 0\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             pre_sum = nums[i]\n",
    "#             if pre_sum == k:\n",
    "#                 res += 1\n",
    "#             for j in range(i + 1, n):\n",
    "#                 pre_sum += nums[j]\n",
    "#                 if pre_sum == k:\n",
    "#                     res += 1\n",
    "#         return res\n",
    "class Solution:\n",
    "    # 使用字典优化, 空间换时间\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = pre_sum = 0\n",
    "        dic = {0 : 1}\n",
    "        for num in nums:\n",
    "            pre_sum += num\n",
    "            res += dic.get(pre_sum - k, 0)\n",
    "            dic[pre_sum] = dic.get(pre_sum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 基础版本\n",
    "        # mem = [0]\n",
    "        # for n in nums:\n",
    "        #     mem.append(mem[-1] + n)\n",
    "        #\n",
    "        # n = len(mem)\n",
    "        # ans = 0\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(i):\n",
    "        #         if mem[i] - mem[j] == k:\n",
    "        #             ans += 1\n",
    "        # return ans\n",
    "\n",
    "        # TLE 改进版本 => mem[j] == mem[i] - k 查找\n",
    "        mem = {0: 1}\n",
    "        ans, sum_n = 0, 0\n",
    "        for n in nums:\n",
    "            sum_n += n\n",
    "            ans += mem.get(sum_n - k, 0)\n",
    "            mem[sum_n] = mem.get(sum_n, 0) + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ret = pre_sum = 0\n",
    "        pre_dict = {0: 1}\n",
    "        for i in nums:\n",
    "            pre_sum += i\n",
    "            ret += pre_dict.get(pre_sum - k, 0)\n",
    "            pre_dict[pre_sum] = pre_dict.get(pre_sum, 0) + 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ret = pre_sum = 0\n",
    "        pre_dict = {0: 1}\n",
    "        for i in nums:\n",
    "            pre_sum += i\n",
    "            ret += pre_dict.get(pre_sum - k, 0)\n",
    "            pre_dict[pre_sum] = pre_dict.get(pre_sum, 0) + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        pre_sum_map = {0: 1}\n",
    "        prev_sum = 0\n",
    "        for num in nums:\n",
    "            prev_sum += num\n",
    "            if prev_sum - k in pre_sum_map:\n",
    "                ans += pre_sum_map[prev_sum - k]\n",
    "            pre_sum_map[prev_sum] = pre_sum_map.get(prev_sum, 0) + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Prefix sum + hashmap. Time O(n) Space O(n)\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # the sum of the first i elems: number of i satisfying this condition\n",
    "        prefix = {0: 1}\n",
    "        curSum = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            if curSum - k in prefix.keys():\n",
    "                res += prefix[curSum - k]\n",
    "            prefix[curSum] = prefix.get(curSum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "#         cnt = 0\n",
    "#         for i in range(len(nums)):\n",
    "#             num_sum = nums[i]\n",
    "#             if num_sum == k:\n",
    "#                 cnt += 1\n",
    "#             for j in range(i-1, -1, -1):\n",
    "#                 num_sum += nums[j]\n",
    "#                 if num_sum == k:\n",
    "#                     cnt += 1\n",
    "#         return cnt \n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        pre, cnt = 0, 0                          \n",
    "        dct = {0: 1}\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            if pre - k in dct:\n",
    "                cnt += dct[pre - k]\n",
    "            if pre in dct:\n",
    "                dct[pre] += 1\n",
    "            else:\n",
    "                dct[pre] = 1\n",
    "            \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        count = 0 \n",
    "        cumsum = 0 \n",
    "        sum_freq = {0:1}\n",
    "        for num in nums:\n",
    "            cumsum += num\n",
    "            if cumsum - k in sum_freq:\n",
    "                count += sum_freq.get(cumsum - k,0) \n",
    "            sum_freq[cumsum] = sum_freq.get(cumsum,0) + 1 \n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        sum2cnt = {0: 1}\n",
    "\n",
    "        res = 0\n",
    "        cur_sum = 0\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            # 左开右闭区间\n",
    "            cur_sum += nums[right]\n",
    "\n",
    "            if cur_sum - k in sum2cnt:\n",
    "                res += sum2cnt.get(cur_sum - k, 0)\n",
    "            \n",
    "            sum2cnt[cur_sum] = sum2cnt.get(cur_sum, 0) + 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if nums is None or len(nums)==0 or k is None:\n",
    "            return 0\n",
    "        from collections import defaultdict \n",
    "        track = defaultdict(int)\n",
    "        track[0] = 1\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for v in nums:\n",
    "            cur += v\n",
    "            if cur-k in track:\n",
    "                ans += track[cur-k]\n",
    "               \n",
    "            track[cur] += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口,不太行，因为不满足单调性，还是hashmap双指针吧\n",
    "        # left = 0 \n",
    "        # sum_num = 0 \n",
    "        # for right in range(len(nums)):\n",
    "        #     sum_num += nums[right]\n",
    "        #     while sum_num > k\n",
    "\n",
    "        prefix = [0]*(len(nums)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        hashmap = {}\n",
    "        res = 0 \n",
    "        for i in prefix:\n",
    "            if i - k in hashmap:\n",
    "                res += hashmap[i - k]\n",
    "            if i in hashmap:\n",
    "                hashmap[i] += 1\n",
    "            else:\n",
    "                hashmap[i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums, k):\n",
    "        result_num, pre_sum=0, 0\n",
    "        pre_dict={0:1}\n",
    "        for item in nums:\n",
    "            pre_sum+=item\n",
    "            result_num+=pre_dict.get(pre_sum-k,0)\n",
    "            pre_dict[pre_sum]=pre_dict.get(pre_sum,0)+1\n",
    "        return result_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #前缀和+hash表优化\n",
    "        presum2times={}\n",
    "        presum2times[0]=1\n",
    "        cnt,pre=0,0\n",
    "        for x in nums:\n",
    "            pre+=x\n",
    "            if pre-k in presum2times:cnt+=presum2times[pre-k]\n",
    "            if pre in presum2times:presum2times[pre]+=1\n",
    "            else:presum2times[pre]=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [0 for _ in range(n+1)]\n",
    "        m = {0:1}\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            prefix[i] = nums[i-1] + prefix[i-1]\n",
    "            remain = prefix[i] - k\n",
    "            if remain in m:\n",
    "                count += m[remain]\n",
    "            \n",
    "            m[prefix[i]] = m.get(prefix[i],0) + 1\n",
    "        \n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1 if nums[0] == k else 0\n",
    "        pre_sum = [0]\n",
    "        pre_sum_dict = {0:1}\n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            \n",
    "            pre_sum.append(pre_sum[-1] + v)\n",
    "            if pre_sum[-1] - k in pre_sum_dict:\n",
    "                ans += pre_sum_dict[pre_sum[-1]-k]\n",
    "            if pre_sum[-1] not in pre_sum_dict:\n",
    "                pre_sum_dict[pre_sum[-1]] = 1\n",
    "            else:\n",
    "                pre_sum_dict[pre_sum[-1]] += 1\n",
    "            # print(pre_sum)\n",
    "            # print(pre_sum_dict)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "        # n = len(pre_sum)\n",
    "        # print(pre_sum)\n",
    "        # ans = 0\n",
    "        # for i in range(1,n):\n",
    "        #     for j in range(i):\n",
    "        #         if pre_sum[i] - pre_sum[j] == k:\n",
    "        #             ans += 1\n",
    "\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        from collections import defaultdict\n",
    "\n",
    "        num_sums = list(accumulate(nums))\n",
    "        num_sums.insert(0,0)\n",
    "        sum_d, cnt = defaultdict(int), 0\n",
    "        for i, num_sum in enumerate(num_sums):\n",
    "            if num_sum -k in sum_d:\n",
    "                cnt += sum_d[num_sum-k]\n",
    "            sum_d[num_sum] +=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        la=[0]\n",
    "        for i in nums:\n",
    "            la.append(la[-1]+i)\n",
    "        d=collections.defaultdict(int)\n",
    "        ans=0\n",
    "        for v in la:\n",
    "            t=v-k\n",
    "            if t in d:\n",
    "                ans+=d[t]\n",
    "            d[v]+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = 1\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            res += d[nums[i] - k]\n",
    "            d[nums[i]] += 1\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)==1:\n",
    "            if nums[0]==k:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        dic = {}\n",
    "        dic[0]=1  #  需要初始化0:1，应对此时情况：nums=[1],k=1,当nums[0]-k以后就等于0，此时有一个符合条件的子数组\n",
    "        res = 0\n",
    "        sum_dynamic = 0\n",
    "        for idx in range(0, len(nums)):\n",
    "            sum_dynamic+=nums[idx]\n",
    "            \n",
    "            if dic.get(sum_dynamic-k):\n",
    "                res+=dic[sum_dynamic-k]\n",
    "\n",
    "            if sum_dynamic in dic:\n",
    "                dic[sum_dynamic]+=1\n",
    "            else:\n",
    "                dic[sum_dynamic]=1\n",
    "        print(dic)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = collections.defaultdict(int)\n",
    "        pre_sum[0] = 1\n",
    "        ans,total = 0 , 0\n",
    "        for i in range(n):\n",
    "            ans += pre_sum[total - k + nums[i]]\n",
    "            total += nums[i]\n",
    "            pre_sum[total] += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        prefix = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            prefix[i+1] = prefix[i] + nums[i]\n",
    "        count = {}\n",
    "        res = 0\n",
    "        for i in range(1, len(prefix)):\n",
    "            if prefix[i] not in count.keys():\n",
    "                count[prefix[i]] = 1\n",
    "            else:\n",
    "                count[prefix[i]] += 1\n",
    "            if k == prefix[i]:\n",
    "                res += 1\n",
    "            if prefix[i] - k in count.keys():\n",
    "                if k != 0:\n",
    "                    res += count[prefix[i] - k]\n",
    "                else:\n",
    "                    res += count[prefix[i] - k] - 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        pre_nums = {0: 1}\n",
    "        prev = 0\n",
    "        for num in nums:\n",
    "            prev += num\n",
    "            if prev - k in pre_nums:\n",
    "                ans += pre_nums[prev - k]\n",
    "            pre_nums[prev] = pre_nums.get(prev, 0) + 1\n",
    "        print(pre_nums)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        hash_sum = {0: 1}\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            presum += num\n",
    "            if presum - k in hash_sum:\n",
    "                ans += hash_sum[presum - k]\n",
    "                print(ans)\n",
    "            hash_sum[presum] = hash_sum.get(presum, 0) + 1\n",
    "\n",
    "        print(hash_sum)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            tmp += nums[i]            \n",
    "            ans += cnt[tmp-k]\n",
    "            cnt[tmp] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], target: int) -> int:\n",
    "        presum = 0 # 前缀和\n",
    "        hashmap = defaultdict(int)\n",
    "        hashmap[0] = 1 # dic[key]:value,代表前缀和key出现的次数\n",
    "        ans = 0    \n",
    "        for num in nums:\n",
    "            presum += num\n",
    "            # presum - target 表示以起始点到当前num为终点的前缀和比target多出的距离\n",
    "            ans += hashmap[presum - target]\n",
    "            # ans += dic.get(presum-target,0) \n",
    "            # hashmap[presum] = dic.get(presum,0) + 1 \n",
    "            hashmap[presum] = hashmap[presum] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        prefix_cnt = defaultdict(int)\n",
    "        prefix_cnt[0] = 1\n",
    "        cur_sum = res = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            res += prefix_cnt[cur_sum-k]\n",
    "            prefix_cnt[cur_sum] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #前缀和+hash_map查询\n",
    "        hash_map = {}\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = dp[i-1] + nums[i]\n",
    "        print(dp)\n",
    "        total = 0\n",
    "        #定义hash_map存储\n",
    "        for i in dp:\n",
    "            if i-k in hash_map:\n",
    "                total = total + hash_map[i-k]\n",
    "            \n",
    "            if i==k:\n",
    "                total += 1\n",
    "\n",
    "            if i not in hash_map:\n",
    "                hash_map[i] = 1\n",
    "            else:\n",
    "                hash_map[i] += 1\n",
    "        print(hash_map)\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        Presum = collections.defaultdict(int)\n",
    "        Presum[0]=1\n",
    "        presum=0\n",
    "        for num in nums:\n",
    "            presum+=num\n",
    "            count+=Presum[presum-k] #先判断然后在给前缀和加一\n",
    "            Presum[presum]+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "#         k_dct = dict()\n",
    "#         for i, n in enumerate(nums):\n",
    "#             k_dct[n] = k_dct.get(n, 0) + 1\n",
    "#             s = 0\n",
    "#             for j in range(i):\n",
    "#                 j = i - j - 1\n",
    "#                 s += nums[j]\n",
    "#                 k_dct[n + s] = k_dct.get(n + s, 0) + 1\n",
    "#         return k_dct.get(k, 0)\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        mid = len(nums) // 2\n",
    "        left = {0: 1}\n",
    "        s = 0\n",
    "        for i in range(mid-1, -1, -1):\n",
    "            s += nums[i]\n",
    "            left[s] = left.get(s, 0) + 1\n",
    "        right = {0: 1}\n",
    "        s = 0\n",
    "        for i in range(mid + 1, len(nums)):\n",
    "            s += nums[i]\n",
    "            right[s] = right.get(s, 0) + 1\n",
    "        out = 0\n",
    "        for l in left.keys():\n",
    "            r = k - l - nums[mid]\n",
    "            out += left.get(l, 0) * right.get(r, 0)\n",
    "        out += self.subarraySum(nums[:mid], k)\n",
    "        out += self.subarraySum(nums[mid+1:], k)\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        wc = defaultdict(int)\n",
    "        wc[0] = 1\n",
    "        ret = 0\n",
    "        pre = 0\n",
    "        for n in nums:\n",
    "            pre += n\n",
    "            if wc[pre - k] > 0:\n",
    "                ret += wc[pre - k]\n",
    "            wc[pre] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        i=0\n",
    "        j=0\n",
    "        n=len(nums)\n",
    "        sm=0\n",
    "        out=0\n",
    "        dp=defaultdict(int)\n",
    "        sm=0\n",
    "        dp[0]+=1\n",
    "        for i in range(n):\n",
    "            sm+=nums[i]\n",
    "            out+=dp[sm-k]\n",
    "            dp[sm]+=1\n",
    "        return out\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        record = collections.OrderedDict()\n",
    "        pre = 0\n",
    "        count = 0\n",
    "        record[0] = 1\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in record:\n",
    "                count += record[pre - k]#找到前缀和为这个的数量,因为和为k也就代表剩下的是pre - k,pre球的是前缀和\n",
    "                #record[pre] += 1\n",
    "            #else:\n",
    "            if pre in record:\n",
    "                record[pre] += 1\n",
    "            else:\n",
    "                record[pre] = 1\n",
    "        return count\n",
    "\n",
    "\n",
    "        # sum_i = [0]\n",
    "        # for i in range(n):\n",
    "        #     sum_i.append(sum(nums[:i + 1]))\n",
    "        # #print(sum_i)\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(i):\n",
    "        #         #print(nums[j:i + 1])\n",
    "        #         #print(sum_i[i], sum_i[j])\n",
    "        #         if sum_i[i] - sum_i[j] == k:\n",
    "        #             res += 1\n",
    "        # return res\n",
    "\n",
    "        #nums = sorted(nums)\n",
    "        # n = len(nums)\n",
    "        # if len(nums) == 1:\n",
    "        #     if sum(nums) == k:\n",
    "        #         return 1\n",
    "        #     return 0\n",
    "        # start = 0\n",
    "        # end = 1\n",
    "        # res = 0\n",
    "        # while(start <= end and end < n):\n",
    "        #     if sum(nums[start:end + 1]) < k:\n",
    "        #         end += 1\n",
    "        #     elif sum(nums[start:end + 1]) > k:\n",
    "        #         start += 1\n",
    "        #     else:\n",
    "        #         res += 1\n",
    "        #         start = end = start + 1\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        dic = defaultdict(int)\n",
    "        dic[0] = 1\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            target = pre-k\n",
    "            res += dic[target]\n",
    "            dic[pre] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        sums = [0]*(len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0:\n",
    "                sums[i] = sums[i - 1] + nums[i]\n",
    "            else:\n",
    "                sums[i] = nums[i]\n",
    "            \n",
    "        def get_sum(i,j):\n",
    "            if i > 0:\n",
    "                return sums[j] - sums[i - 1]\n",
    "            return sums[j]\n",
    "        pre = 0\n",
    "        cnt = Counter()\n",
    "        cnt[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            pre += nums[i]\n",
    "            ans += cnt[pre - k]\n",
    "            cnt[pre] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        presum = collections.defaultdict(int)\n",
    "        presum[0] = 1\n",
    "        res = 0\n",
    "\n",
    "\n",
    "        p = 0\n",
    "        for i in range(n):\n",
    "            p+=nums[i]\n",
    "            \n",
    "            res+=presum[p-k]\n",
    "            presum[p]+=1\n",
    "\n",
    "            # l,r = 0,i-1\n",
    "            # while l<r:\n",
    "            #     mid = (l+r+1)//2\n",
    "            #     if presum[mid]<=presum[i]-k:\n",
    "            #         l = mid\n",
    "            #     else:\n",
    "            #         r = mid-1\n",
    "            # right = l\n",
    "            # if presum[i]-presum[right]!=k:\n",
    "            #     continue\n",
    "\n",
    "            # while l<r:\n",
    "            #     mid = (l+r)//2\n",
    "            #     if presum[mid]>=presum[i]-k:\n",
    "            #         r = mid\n",
    "            #     else:\n",
    "            #         l = mid+1\n",
    "\n",
    "            # left = l\n",
    "            # res+=right-left+1\n",
    "            \n",
    "        # print(presum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # nums[i] may < 0 !\n",
    "        ans = prefixSum = 0\n",
    "        sumCnt = defaultdict(int)\n",
    "        sumCnt[0] = 1\n",
    "        for num in nums:\n",
    "            prefixSum += num\n",
    "            ans += sumCnt[prefixSum - k]\n",
    "            sumCnt[prefixSum] += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "0, 1\n",
    "0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0 for _ in range(n + 1)]\n",
    "        cnt = 0\n",
    "\n",
    "        s[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            s[i] = s[i-1] + nums[i-1]\n",
    "            \n",
    "        c = Counter(s)\n",
    "        c1 = Counter()\n",
    "        if k != 0:\n",
    "            for num in s:\n",
    "                c1[num] += 1\n",
    "                cnt += c[num+k] - c1[num+k]\n",
    "        else:\n",
    "            for k, v in c.items():\n",
    "                cnt += v*(v-1)//2 \n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        s=[0]\n",
    "        dic=defaultdict(int)\n",
    "        dic[0]=1\n",
    "        ans=0\n",
    "        for x in nums:\n",
    "            s.append(s[-1]+x)\n",
    "            ans+=dic[s[-1]-k]\n",
    "            dic[s[-1]]+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        hashmap = {0:[-1]}\n",
    "        res, tmp = 0, 0\n",
    "        for i in range(n):\n",
    "            tmp += nums[i]\n",
    "            if tmp - k in hashmap:\n",
    "                res += len(hashmap[tmp - k])\n",
    "            if tmp in hashmap:\n",
    "                hashmap[tmp].append(i)\n",
    "            else:\n",
    "                hashmap[tmp] = [i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        presum = [0]\n",
    "        dic[0] +=1\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            presum.append(presum[-1]+nums[i-1])\n",
    "            dic[presum[-1]] += 1\n",
    "            res += dic[presum[-1]-k]\n",
    "            if k == 0:\n",
    "                res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "        rec = defaultdict(int)\n",
    "        rec[0] += 1\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "            rec[presum[i+1]] += 1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(0, n):\n",
    "            s = presum[i]\n",
    "            rec[s] -= 1\n",
    "            ans += rec[s+k]\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        sum_list = [0] * len(nums)\n",
    "        sum_list[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            sum_list[i] = sum_list[i-1] + nums[i]\n",
    "        dt = {}\n",
    "        res = 0\n",
    "        for i in range(len(sum_list)):\n",
    "            if sum_list[i] == k:\n",
    "                res += 1\n",
    "            t = sum_list[i] - k\n",
    "            if dt.get(t):\n",
    "                res += len(dt[t])\n",
    "            if not dt.get(sum_list[i]):\n",
    "                dt[sum_list[i]] = []\n",
    "            dt[sum_list[i]].append(i)\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        acc = list(accumulate(nums,initial=0))\n",
    "        d = defaultdict(int)\n",
    "        d[0] = 1\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            # acc[i+1] - acc[j] == k \n",
    "            ans += d[acc[i+1]-k]\n",
    "            d[acc[i+1]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #一眼前缀和\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        n=len(nums)\n",
    "        x=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(n+1):\n",
    "            if arr[i] in x:\n",
    "                ans+=x[arr[i]]\n",
    "            #找arr[j]\n",
    "            cur=arr[i]+k\n",
    "            x[cur]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        sm = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            sm[i] = sm[i-1] + nums[i-1]\n",
    "\n",
    "        res = 0\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(int)\n",
    "        for i in range(n+1):\n",
    "            if sm[i] in dct:\n",
    "                res += dct[sm[i]]\n",
    "            dct[sm[i] + k] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #一眼前缀和\n",
    "        #而且有负数值,不适合用滑动窗口\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        n=len(nums)\n",
    "        x=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(n+1):\n",
    "            if arr[i] in x:\n",
    "                ans+=x[arr[i]]\n",
    "            #找arr[j]\n",
    "            cur=arr[i]+k\n",
    "            x[cur]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #一眼前缀和\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        n=len(nums)\n",
    "        x=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(n+1):\n",
    "            if arr[i] in x:\n",
    "                ans+=x[arr[i]]\n",
    "            #找arr[j]\n",
    "            cur=arr[i]+k\n",
    "            x[cur]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        s=[0]\n",
    "        dic=defaultdict(list)\n",
    "        for i,x in enumerate(nums):\n",
    "            s.append(s[-1]+x)\n",
    "            dic[s[-1]].append(i+1)\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if s[i]+k in dic:\n",
    "                arr=dic[s[i]+k]\n",
    "                l=len(arr)\n",
    "                j=self.lb(arr,i,l)\n",
    "                ans+=l-j\n",
    "                if j<l and arr[j]==i:\n",
    "                    ans-=1\n",
    "        return ans\n",
    "\n",
    "    def lb(self,arr,x,n):\n",
    "        l,r=0,n\n",
    "        while l<r:\n",
    "            m=(l+r)>>1\n",
    "            if arr[m]>x:\n",
    "                r=m\n",
    "            elif arr[m]<x:\n",
    "                l=m+1\n",
    "            else:\n",
    "                r=m\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #一眼前缀和\n",
    "        #arr[j]-arr[i]==k\n",
    "        #而且有负数值,不适合用滑动窗口\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        n=len(nums)\n",
    "        x=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(n+1):\n",
    "            if arr[i] in x:\n",
    "                ans+=x[arr[i]]\n",
    "            #找arr[j]\n",
    "            cur=arr[i]+k\n",
    "            x[cur]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        record=defaultdict(list)\n",
    "        record[0].append(0)\n",
    "        sum=[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            t=sum[-1]+nums[i-1]\n",
    "            sum.append(t)\n",
    "            record[t].append(i)\n",
    "        res=0\n",
    "        for var in range(len(nums)):\n",
    "            if sum[var]+nums[var]-k in record.keys():\n",
    "                for j in record[sum[var]+nums[var]-k]:\n",
    "                    if j<=var:\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        #\n",
    "        r = 0\n",
    "        m = {}\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] = pre_sum[i-1] + nums[i-1]\n",
    "            key1 = str(pre_sum[i-1] + k)\n",
    "            m.setdefault(key1, 0)\n",
    "            m[key1] += 1\n",
    "            #\n",
    "            key2 = str(pre_sum[i])\n",
    "            r += m.get(key2, 0)\n",
    "        # \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        record = collections.defaultdict(list)\n",
    "        prefix = 0\n",
    "        res = 0\n",
    "        record[0].append(-1)\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if prefix-k in record:\n",
    "                res += len(record[prefix-k])\n",
    "            record[prefix].append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        s=[0]\n",
    "        dic=defaultdict(list)\n",
    "        for i,x in enumerate(nums):\n",
    "            s.append(s[-1]+x)\n",
    "            dic[s[-1]].append(i+1)\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if s[i]+k in dic:\n",
    "                arr=dic[s[i]+k]\n",
    "                l=len(arr)\n",
    "                j=self.lb(arr,i,l)\n",
    "                ans+=l-j\n",
    "                if j<l and arr[j]==i:\n",
    "                    ans-=1\n",
    "        return ans\n",
    "\n",
    "    def lb(self,arr,x,n):\n",
    "        l,r=0,n\n",
    "        while l<r:\n",
    "            m=(l+r)>>1\n",
    "            if arr[m]>x:\n",
    "                r=m\n",
    "            elif arr[m]<x:\n",
    "                l=m+1\n",
    "            else:\n",
    "                r=m\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        hm = {}\n",
    "        s = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            if s not in hm:\n",
    "                hm[s] = []\n",
    "            hm[s].append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for v, l1 in hm.items():\n",
    "            if v == k:\n",
    "                ans += len(l1)\n",
    "            if v+k in hm:\n",
    "                l2 = hm[v+k]\n",
    "                for i in l1:\n",
    "                    for j in l2:\n",
    "                        if j > i:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = 1\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            result += d[nums[i] - k]\n",
    "            d[nums[i]] += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dc = defaultdict(list)\n",
    "        sm = 0\n",
    "        dc[0].append(0)\n",
    "        for i, v in enumerate(nums,start=1):\n",
    "            sm += v\n",
    "            dc[sm].append(i)\n",
    "        cnt = 0\n",
    "        if k:\n",
    "            for i, vlis in dc.items():\n",
    "                if k+i in dc:\n",
    "                    rlis = dc[k+i]\n",
    "                    i, ni, j, nj = 0, len(vlis), 0, len(rlis)\n",
    "                    while i<ni and j<nj:\n",
    "                        if vlis[i]<rlis[j]:\n",
    "                            cnt += nj-j\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            j += 1\n",
    "        else:\n",
    "            for i,vlis in dc.items():\n",
    "                nv = len(vlis)\n",
    "                cnt += (nv-1)*nv//2\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i-1]\n",
    "        \n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += mp[num - k]\n",
    "            mp[num] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dc = defaultdict(list)\n",
    "        sm = 0\n",
    "        dc[0].append(0)\n",
    "        for i, v in enumerate(nums,start=1):\n",
    "            sm += v\n",
    "            dc[sm].append(i)\n",
    "        cnt = 0\n",
    "        if k:\n",
    "            for i, vlis in dc.items():\n",
    "                if k+i in dc:\n",
    "                    rlis = dc[k+i]\n",
    "                    i, ni, j, nj = 0, len(vlis), 0, len(rlis)\n",
    "                    while i<ni and j<nj:\n",
    "                        if vlis[i]<rlis[j]:\n",
    "                            cnt += nj-j\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            j += 1\n",
    "        else:\n",
    "            for i,vlis in dc.items():\n",
    "                nv = len(vlis)\n",
    "                cnt += (nv-1)*nv//2\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i - 1]\n",
    "        ans = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            ans += cnt[nums[i] - k]\n",
    "            cnt[nums[i]] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = 1\n",
    "        result += d[nums[0] - k]\n",
    "        d[nums[0]] += 1\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i-1]\n",
    "            result += d[nums[i] - k]\n",
    "            d[nums[i]] += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = defaultdict(int)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        presum[0] = 1\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            res += presum[cur-k]\n",
    "            presum[cur] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans=result=0\n",
    "        dict_map=defaultdict(int)\n",
    "        dict_map[0]=1\n",
    "        for i in range(len(nums)):\n",
    "            result+=nums[i]\n",
    "            ans+=dict_map[result-k]\n",
    "            dict_map[result]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        mp = dict()\n",
    "        pre = 0\n",
    "        mp_set = set()\n",
    "        ans = 0\n",
    "        mp[0] = 1\n",
    "        mp_set.add(0)\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            if pre - k in mp_set:\n",
    "                ans += mp[pre - k]\n",
    "            if pre in mp_set:\n",
    "                mp[pre] += 1\n",
    "            else:\n",
    "                mp[pre] = 1\n",
    "                mp_set.add(pre)\n",
    "                \n",
    "            \n",
    "        return ans\n",
    " \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        prefix = defaultdict(int)\n",
    "        prefix[0] = 1\n",
    "        summation = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            summation += num\n",
    "            ans += prefix[summation - k]\n",
    "            prefix[summation] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = defaultdict(int)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        presum[0] = 1\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            res += presum[cur-k]\n",
    "            presum[cur] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        suffix_sum_tmp = 0\n",
    "        suffix_sum_dict = defaultdict(int)\n",
    "        rs = 0\n",
    "        for num in nums:  # 前向走一遍，存前缀和并将以此为右边界的区间数计数\n",
    "            suffix_sum_tmp += num\n",
    "            if suffix_sum_tmp==k:\n",
    "                rs += 1\n",
    "            # 以当前数为右边界的连续子区间存在，则算入计数\n",
    "            rs += suffix_sum_dict[suffix_sum_tmp-k]\n",
    "            \n",
    "            suffix_sum_dict[suffix_sum_tmp] += 1  # 到当前位置前缀和为suffix_sum_tmp的个数+1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        prefix = defaultdict(int)\n",
    "        summation = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            summation += num\n",
    "            if summation == k:\n",
    "                ans += 1\n",
    "            ans += prefix[summation - k]\n",
    "            prefix[summation] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        dict_=defaultdict(int)\n",
    "        dict_[0]=1\n",
    "        local_sum=0\n",
    "        cnt=0\n",
    "\n",
    "        for x in nums:\n",
    "            local_sum+=x\n",
    "           \n",
    "            target=local_sum-k\n",
    "            cnt+=dict_[target]\n",
    "            dict_[local_sum]+=1\n",
    "            \n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        pre_sum_map = defaultdict(int)\n",
    "        pre_sum_map[0] = 1\n",
    "        pre_sum = 0\n",
    "\n",
    "        for n in nums:\n",
    "            pre_sum += n\n",
    "            ans += pre_sum_map[pre_sum - k]\n",
    "            pre_sum_map[pre_sum] += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        pre = collections.defaultdict(int)\n",
    "        pre[0] = 1\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            ans += pre[cur-k]\n",
    "            pre[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        mem = defaultdict(int)\n",
    "\n",
    "        sum_ = 0\n",
    "        \n",
    "        mem[sum_] += 1\n",
    "\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            sum_ += num\n",
    "            ret += mem[sum_ - k]\n",
    "            mem[sum_] += 1\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum_dict = collections.defaultdict(int)\n",
    "        cursum = 0\n",
    "        result = 0\n",
    "        presum_dict[0] = 1\n",
    "        for num in nums:\n",
    "            cursum += num\n",
    "            result += presum_dict[cursum - k]\n",
    "            presum_dict[cursum] += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "    r = defaultdict(lambda:0)\n",
    "    s = 0\n",
    "    r[0] = 1\n",
    "    ret = 0\n",
    "    for n in nums:\n",
    "      s += n\n",
    "      ret += r[s - k]\n",
    "      r[s] += 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        s, count = [0],0\n",
    "        from collections import defaultdict\n",
    "        ex = defaultdict(int)\n",
    "        ex[0] = 1\n",
    "        for x in nums:\n",
    "            s.append(s[-1] + x)\n",
    "            \n",
    "            count += ex[s[-1]-k]\n",
    "            ex[s[-1]] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = 1\n",
    "        for n in nums:\n",
    "            presum += n\n",
    "            ans += d[presum - k]\n",
    "            d[presum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        csum = [0]\n",
    "        for i in nums:\n",
    "            csum.append(csum[-1]+i)\n",
    "        rec = {}\n",
    "        for i, v in enumerate(csum):\n",
    "            if v not in rec:\n",
    "                rec[v] = [i]\n",
    "            else:\n",
    "                rec[v].append(i)\n",
    "        def bi_search(l, val):\n",
    "            len_ = len(l)\n",
    "            if len_ >10:\n",
    "                lft, rht = -1, len_ \n",
    "                while lft+1!=rht:\n",
    "                    mid = int((lft+rht)/2)\n",
    "                    if l[mid]<val:\n",
    "                        lft = mid \n",
    "                    else:\n",
    "                        rht = mid\n",
    "                return lft +1 \n",
    "            else: \n",
    "                cnt_ = 0\n",
    "                for j in l:\n",
    "                    if j < val:\n",
    "                        cnt_ +=1\n",
    "                return cnt_ \n",
    "    \n",
    "        def count(x, y):\n",
    "            r = 0\n",
    "            for i in y:\n",
    "                r += bi_search(x, i)\n",
    "            return r \n",
    "\n",
    "\n",
    "        cnt =0\n",
    "        for val in rec.keys():\n",
    "            l = val-k\n",
    "            if l in rec:\n",
    "                x = rec[l]\n",
    "                y = rec[val]\n",
    "                cnt += count(x, y)\n",
    "\n",
    "        return cnt \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # memo = [nums[0]]\n",
    "\n",
    "        # for i, v in enumerate(nums[1:]):\n",
    "        #     memo.append(memo[-1]+v)\n",
    "        # len_ = len(nums)\n",
    "        # cnt = 0\n",
    "        # for i, vi in enumerate(nums):\n",
    "        #     if i>0 :\n",
    "        #         j = i  \n",
    "        #         while j< len_:\n",
    "        #             sum_ = memo[j]-memo[i-1]\n",
    "        #             if sum_==k:\n",
    "        #                 cnt += 1\n",
    "        #             j +=1 \n",
    "        #     elif i==0:\n",
    "        #             for j in memo:\n",
    "        #                 if j == k:\n",
    "        #                     cnt +=1\n",
    " \n",
    "        # return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
    "        preSums = collections.defaultdict(int)\n",
    "        presum = 0\n",
    "        count = 0\n",
    "        preSums[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "            count += preSums[presum - k]\n",
    "            print(count)\n",
    "            preSums[presum]+= 1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
